# Copyright 2013, Michael H. Goldwasser
#
# Developed for use with the book:
#
#    Data Structures and Algorithms in Python
#    Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
#    John Wiley & Sons, 2013
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.


class _DoublyLinkedBase(object):
	"""A base class providing a doubly linked list representation."""

	# -------------------------- nested _Node class --------------------------
	# nested _Node class
	class _Node(object):
		"""Lightweight, nonpublic class for storing a doubly linked node."""
		__slots__ = '_element', '_prev', '_next'  # streamline memory

		def __init__(self, element, prev, next):  # initialize node's fields
			self._element = element  # user's element
			self._prev = prev  # previous node reference
			self._next = next  # next node reference

	# -------------------------- list constructor --------------------------

	def __init__(self):
		"""Create an empty list."""
		self._header = self._Node(None, None, None)
		self._trailer = self._Node(None, None, None)
		self._header._next = self._trailer  # trailer is after header
		self._trailer._prev = self._header  # header is before trailer
		self._size = 0  # number of elements

	# -------------------------- public accessors --------------------------

	def __len__(self):
		"""Return the number of elements in the list."""
		return self._size

	def is_empty(self):
		"""Return True if list is empty."""
		return self._size == 0

	# -------------------------- nonpublic utilities --------------------------

	def _insert_between(self, e, predecessor, successor):
		"""Add element e between two existing nodes and return new node."""
		newest = self._Node(e, predecessor, successor)  # linked to neighbors
		predecessor._next = newest
		successor._prev = newest
		self._size += 1
		return newest

	def _delete_node(self, node):
		"""Delete nonsentinel node from the list and return its element."""
		predecessor = node._prev
		successor = node._next
		predecessor._next = successor
		successor._prev = predecessor
		self._size -= 1
		element = node._element  # record deleted element
		node._prev = node._next = node._element = None  # deprecate node
		return element  # return deleted element
